9025. k-ый элемент

 

Задан целочисленный массив а из n элементов и число k. Выведите k-ый элемент в отсортированном массиве a (нумерация массива начинается с 1).

 

Вход. Первая строка содержит два числа n и k (1 ≤ n ≤ 2000, 1 ≤ k ≤ n). Вторая строка содержит n целых чисел ai (1 ≤ i ≤ n, 1 ≤ ai ≤ 2000).

 

Выход. Выведите k-ый элемент в отсортированном массиве а.

 

Пример входа 1

Пример выхода 1

2 1

2 1

1

 

 

Пример входа 2

Пример выхода 2

5 3

4 7 1 8 12

7

 

 

РЕШЕНИЕ

k-ая статистика

 

Анализ алгоритма

Для решения задачи за O(nlog2n) достаточно отсортировать массив и вывести его k-ый элемент.

 

Можно воспользоваться функцией nth_element, которая за O(n) переставляет элементы массива а таким образом, что на k-ом месте находится k-ый элемент, числа, стоящие слева от него, не больше a[k], а числа, стоящие справа от него, не меньше a[k].

 

k-ую статистику можно найти за линейное время при помощи функции разбиения массива (partition), которая используется в алгоритме быстрой сортировки. Функция partition за линейное время разбивает (не сортирует) массив a[1..n] на две части a[1..pos] и a[pos + 1..n] так, что все элементы массива из первой части не больше элементов из второй. Если k ≤ pos, то делее k-ую статистику ищем в a[1..pos], иначе – в a[pos + 1..n]

 

Реализация алгоритма

Объявим рабочий массив.

 

vector<int> v;

 

Читаем входные массивы.

 

scanf("%d %d", &n, &k);

v.resize(n + 1);

for (i = 1; i <= n; i++)

  scanf("%d", &v[i]);

 

Сортируем массив, начиная с 1 позиции.

 

sort(v.begin() + 1, v.end());

 

Выводим k-ый элемент.

 

printf("%d\n", v[k]);

 

Реализация алгоритма – nth_element

 

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

 

vector<int> v;

int n, k, i;

 

int main(void)

{

  scanf("%d %d", &n, &k);

  v.resize(n + 1);

  for (i = 1; i <= n; i++)

    scanf("%d", &v[i]);

 

  nth_element(v.begin() + 1, v.begin() + k, v.end());

  printf("%d\n", v[k]);

  return 0;

}

 

Реализация алгоритма – поиск k-го минимума при помощи очереди с приоритетами

 

#include <cstdio>

#include <queue>

using namespace std;

 

Очередь с приоритетами является max кучей и хранит только k наименьших элементов.

 

priority_queue<int> pq;

int i, n, k, x;

 

int main(void)

{

 

Читаем входные данные.

 

  scanf("%d %d", &n, &k);

  for (i = 1; i <= n; i++)

  {

 

Читаем элемент, заносим его в кучу.

 

    scanf("%d", &x);

    pq.push(x);

 

Как только куча будет содержать больше k элементов, удаляем один элемент.

 

    if (i > k) pq.pop(); // only k elements in the pq at any time

  }

 

После обработки входного массива на вершине кучи будет находиться наибольший из k наименьших элементов массива. Это и есть k-ый элемент в отсортированном по неубыванию массиве.

 

  printf("%d\n", pq.top());

  return 0;

}

 

Реализация алгоритма – поиск k-ой статистики

 

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

 

vector<int> v;

int n, k, i;

 

int Partition(int left, int right)

{

  int x = v[left], i = left - 1, j = right + 1;

  while (1)

  {

    do j--; while (v[j] > x);

    do i++; while (v[i] < x);

    if (i < j) swap(v[i], v[j]); else return j;

  }

}

 

int kth(int k, int left, int right)

{

  if (left == right) return v[left];

  int pos = Partition(left, right);

  if (k <= pos) return kth(k, left, pos);

  else return kth(k, pos + 1, right);

}

 

int main(void)

{

  scanf("%d %d", &n, &k);

  v.resize(n + 1);

  for (i = 1; i <= n; i++)

    scanf("%d", &v[i]);

 

  printf("%d\n", kth(k, 1, n));

  return 0;

}

 

Java реализация

 

import java.util.*;

 

public class Main

{

  static void swap(int a[], int i, int j)

  {

    int temp = a[i];  a[i] = a[j]; a[j] = temp;

  }

 

  static int Partition(int a[], int L, int R)

  {

    int x = a[L];

    int i = L - 1, j = R + 1;

    while (true)

    {

      do j--; while (a[j] > x);

      do i++; while (a[i] < x);

      if (i < j) swap(a, i, j); else return j;

    }

  }

 

  static int kth(int a[], int k, int left, int right)

  {

    if (left == right) return a[left];

    int pos = Partition(a, left, right);

    if (k <= pos) return kth(a, k, left, pos);

    else return kth(a, k, pos + 1, right);

  }

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int k = con.nextInt();

    int[] m = new int[n+1];

 

    for (int i = 1; i <= n; i++)

      m[i] = con.nextInt();

 

    System.out.println(kth(m, k, 1, n));

    con.close();

  }

}

 

Python реализация

 

def Partition(lst, left, right):

  x = lst[left]

  i = left – 1

  j = right + 1

  while (True):

    while(True):

      j -= 1;

      if lst[j] <= x: break

    while(True):

      i += 1;

      if lst[i] >= x: break

    if i < j: lst[i], lst[j] =  lst[j], lst[i]

    else: return j;

 

def kth(lst, k, left, right):

  if left == right: return lst[left];

  pos = Partition(lst, left, right);

  if k <= pos: return kth(lst, k, left, pos);

  else: return kth(lst, k, pos + 1, right);

 

n, k = map(int,input().split())

lst = list(map(int,input().split()))

res = kth(lst, k - 1, 0, n - 1)

print(res)